/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/repeated-dna-sequences
   @Language: C++
   @Datetime: 19-12-03 14:11
   */

// Method 1, direct hash, Time 64ms 81%, Space 24.4MB 17.5%
class Solution {
public:
	vector<string> findRepeatedDnaSequences(string s) {
		vector<string> vs;
		unordered_map<string,int> freqs;
		for(int i=0; i+10<=s.length(); freqs[s.substr(i++,10)]++);
		for(const auto &p:freqs)
			if(p.second>1) vs.push_back(p.first);
		return vs;
	}
};

// Method 2, char to int hash, Time 56ms, 87%, Space 16.6MB 85%
class Solution {
public:
	vector<string> findRepeatedDnaSequences(string s) {
		if(s.length()<10) return {};
		unordered_map<char,int> dict={{'A',0},{'C',1},{'G',2},{'T',3}};
		int key=0, K=(1<<20)-1;
		for(int i=0; i<9; key=(key<<2)|dict[s[i++]]);
		vector<string> vs;
		unordered_map<int,int> freqs;
		for(int i=9; i<s.length(); ++i){
			key = K & (key<<2) | dict[s[i]];
			++freqs[key];
			if(freqs[key]==2) vs.push_back(s.substr(i-9,10));
		}
		return vs;
	}
};
